#include <string>
#include <vector>
using namespace std;
class Solution
{
private:
    // 手撕tire tree
    struct tire_node
    {
        tire_node(char c = '\0') : ch(c), sons(26, nullptr) { ; }
        tire_node *get_son(const char c)
        {
            return sons[c - 'a'];
        }
        tire_node *create_son(const char c)
        {
            return sons[c - 'a'] = new tire_node(c);
        }
        void add_end()
        {
            end_num++;
        }
        size_t get_end_num()
        {
            return end_num;
        }

    private:
        char ch;
        int end_num = 0;
        tire_node *next = nullptr;
        vector<tire_node *> sons;
    };
    class tire_tree
    {
    public:
        void insert(const string &str)
        {
            tire_node *cur = root;
            for (auto e : str)
            {
                tire_node *son = cur->get_son(e);
                if (!son)
                    son = cur->create_son(e);
                cur = son;
            }
            cur->add_end();
        }
        // 数据清洗方法
        string &wash(string &str)
        {
            tire_node *cur = root;
            size_t i = 0;
            for (auto e : str)
            {
                tire_node *son = cur->get_son(e);
                if (!son)
                    return str;
                cur = son;
                i++;
                if (cur->get_end_num())
                {
                    return str.erase(i);
                }
            }
            return str;
        }

    private:
        tire_node *root = new tire_node();
    };

public:
    string replaceWords(vector<string> &dictionary, string sentence)
    {
        // tire 保存前缀
        tire_tree tire;
        for (auto &e : dictionary)
        {
            tire.insert(e);
        }
        // 分离单词 + 数据清洗
        string washed_str;
        size_t start = 0;
        for (int i = 0; i < sentence.size(); i++)
        {
            if (sentence[i] == ' ')
            {
                string word(sentence.substr(start, i - start));
                washed_str += tire.wash(word);
                washed_str.push_back(' ');
                start = i + 1;
            }
        }
        string last_word(sentence.substr(start));
        washed_str += tire.wash(last_word);
        return washed_str;
    }
};